#ifndef TIM_BST_H
#define TIM_BST_H
#include "tim_stack&tim_queue.h"
#include "tim_bintree.h"
#include "tim_hashtable.h"
#include "tim_algorithm.h"

namespace tim
{
	template<typename K, typename V>
	class BST: public bintree<entry<K, V>>
	{
		protected:
			binnode<entry<K, V>>* hot;//hot结点，定位succ
			virtual binnode<entry<K, V>>* _find(binnode<entry<K, V>>* next, K const& key);//迭代查找
			binnode<entry<K, V>>* removeAt(binnode<entry<K, V>>* x);
			V error = V();

		public:
			BST(K key = K(), V value = V()): bintree<entry<K, V>>(entry<K, V>(key, value)) {};
			virtual int height() {return this->root->height; };
			virtual V& find(K const& key) //对外find接口， 时间复杂度O（
			{
				binnode<entry<K, V>>* temp = _find(this->root, key);
				if (temp != NULL) return temp->data.value;
				else return error;
			};
			virtual binnode<entry<K, V>>* insert(K const& key, V const& value);
			virtual V remove(K const& key);
	};
}

template<typename K, typename V>
tim::binnode<tim::entry<K, V>>* tim::BST<K, V>::_find(tim::binnode<tim::entry<K, V>>* next, K const& key)
{
	hot = NULL;
	while (next != NULL) {
		hot = next;
		if (key < next->data.key) next = next->left;
		else if (key > next->data.key) next = next->right;
		else break;
	}

	return next;
}

template<typename K, typename V>
tim::binnode<tim::entry<K, V>>* tim::BST<K, V>::insert(K const& key, V const& value)
{
	_find(this->root, key);
	tim::binnode<tim::entry<K, V>>* new_node = new binnode<tim::entry<K, V>>(tim::entry<K, V>(key, value), hot);
	if (hot->data.value > value) hot->left = new_node;
	else hot->right = new_node;
	this->update_height_above(new_node);
	this->_size++;

	return new_node;
}

template<typename K, typename V>
tim::binnode<tim::entry<K, V>>* tim::BST<K, V>::removeAt(tim::binnode<tim::entry<K, V>>* x)
{
	tim::binnode<tim::entry<K, V>>* w = x;
	tim::binnode<tim::entry<K, V>>* succ = NULL;

	if (!x->has_lchild())
		succ = x = x->left;
	else if (!x->has_rchild())
		succ = x = x->right;
	else {
		w = w->succ();
		tim::swap(x->data, w->data);
		tim::binnode<tim::entry<K, V>>* u = w->parent;
		((u == x) ? u->right : u->left) = succ = w->right;
	}

	hot = w->parent;
	if (hot->left == w) hot->left = NULL;
	else hot->right = NULL;
	delete w;
	if (succ) succ->parent = hot;
	return succ;
}

template<typename K, typename V>
V tim::BST<K, V>::remove(K const& key)
{
	tim::binnode<tim::entry<K, V>>* x = _find(this->root, key);
	if (!x) return error;

	V temp = x->data.value;
	removeAt(x);
	this->_size--;
	this->update_height_above(hot);
	return temp;
}

#endif
